package 从前序与中序遍历序列构造二叉树;


import javax.swing.tree.TreeNode;

public class Solution {
    public int i = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder, inorder, 0, inorder.length - 1);
    }

    public TreeNode buildTreeChild(int[] preorder, int[] inorder,
                                   int inbegin, int inend) {
        if (inbegin > inend) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[i]);
//找到当前根，在中序遍历的位置
        int rootIndex = findIndex(inorder, inbegin, inend, preorder[i]);
        i++;
        root.left = buildTreeChild(preorder, inorder, inbegin, rootIndex - 1);
        root.right = buildTreeChild(preorder, inorder, rootIndex + 1, inend);
        return root;
    }

    private int findIndex(int[] inorder, int inbegin, int inend, int key) {
        for (int j = inbegin; j <=inend; j++) {
            if (inorder[j] == key) {
                return j;
            }
        }
        return -1;
    }
}
